This invention relates to web cache servers.
One of the major problems that needs to be tackled as the World Wide Web continues its exponential growth is the severe congestion that Web users are experiencing. Although increasing network bandwidth would help, as more information services are moved onto the Web the demand for bandwidth is likely to continue to outstrip supply for the foreseeable future.
Caching has been widely recognized as one of the solutions to this congestion problem, because caching can substantially reduce latency and improve bandwidth efficiency. With extensive use of caching, along with pre-fetching, replication and mirroring, significant traffic reduction can be achieved on bottleneck links.
Caching may take place at various points between a user and the data source. For example, most modern browsers have built-in caching which keeps recently accessed web pages in the PC itself. Proxy caching was incorporated in the CERN httpd, which is one of the oldest Web servers. A CERN server can also chain to another caching server. Most second-generation Web servers, such as Apache, Jigsaw, and NetSite support similar caching functions. A comprehensive report on Web caching can be found in A. Cormack, Web Caching, Technical Report, University of Wales, UK, September 1996.
Another important work on caching, known as the Harvest Cache, is described by A. Chankhunthod, P. Danzig, C. Neerdales, M. Schwartz, and K. Worrell, in A hierarchical Internet object cache, Usenix'96, January 1996. The Harvest cache possesses a hierarchical caching architecture in which cache servers that are positioned at selected points of a large network co-operate with each other using Internet Cache Protocol (ICP). When A Harvest cache server receives a request for an object that is not cached locally, the server queries its neighbors and hierarchical parents to find the sought object. If that object is not found, the cache server directs the request to the object's source.
After the Harvest project ended August 1996, the development of the Harvest cache has been carried out by the Harvest Developers Group as a commercial product, and by National Laboratory for Advanced Networking Research (NLANR). A report on this project can be found in http://www.nlanr.net/Cache/. A similar system was proposed by R. Malpani, J. Lorch, D. Berger, in Making World Wide Web Caching Servers Cooperate, 4th International World Wide Web Conference, Boston, USA, December 1995, where multicasting is used for querying neighbor servers.
Although the Harvest cache represents an advance in the art it, nevertheless, has a number of problems.
One problem is that for each local cache "MISS", the cache server has to send a query message to all its neighbors and parents, and receive a reply from each of them. This represents an overhead of about 200 bytes per neighbor or parent. In a large Harvest cache system with many cache servers or a deep hierarchy, this overhead is high, and represents a particularly inefficient use of resources when the requested object is small. Additionally, the request/reply interaction introduces some latency during the resolution.
Another problem of the Harvest cache is that the search for a cached object is done in a distributed fashion. For each query, all neighbors and parents have to search their caches in parallel, no matter whether the results is a "HIT" or a "MISS" (and a "MISS" is certain for all but, perhaps, one server). Since a final "MISS" cannot be concluded until the slowest cache server responds or the waiting timer expires, a low hit rate at any one of the cache servers slows down the entire system.
Still another problem of the Harvest cache is that there is no explicit cache placement policy. An object may be cached at any of the cache servers. This lack of policy has a number of implications. For example, objects from a same Web site may spread over all cache servers, which forces all cache servers to be searched in order to find out whether an object is cached or not.